/* 
 * Subsets II
 */

#include "../func.h"

vector<vector<int>> subsetWithDup(vector<int> &S) {
    sort(S.begin(), S.end());
    vector<vector<int>> result;
    vector<int> path;

    dfs(S, S.begin(), path, result);
}
void dfs(vector<int> &S, vector<int>::iterator start, vector<int> &path, vector<vector<int>> &result) {
    result.push_back(path);

    for (auto i = start; i < S.end(); ++i) {
        if (i != start && *i == *(i-1))
            continue;
        path.push_back(*i);
        dfs(S, i+1, path, result);
        path.pop_back();
    }
}